package com.cn.algorithm02.class13;

import com.cn.algorithm02.class01.Nodea;

/***
 * @author: hels
 * @description: 返回整棵二叉树的最大距离
 * 树的深度：就是树的层级。空树的深度为0，一个元素的树深度为1
 * 节点的高度：从叶子节点开始向上数，从1开始
 **/
public class C04_MaxDistance {
    public static void main(String[] args) {
        int[] arr = {6,3,9,2,5};
        Nodea head = Nodea.getNodeInstance(arr);
        head.right = null;
        Nodea l1 = new Nodea(3);
        Nodea l2 = new Nodea(3);
        head.left.left.left = l1;
        head.left.right.left = l2;
        Nodea.printTree(head);
        System.out.println(maxDistance(head));
    }

    public static int maxDistance(Nodea head) {
        return process(head).maxDistance;
    }

    public static Info process(Nodea x) {
        if (x == null) return new Info(0, 0);

        Info leftInfo = process(x.left);
        Info rightInfo = process(x.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        // 找出三种最远距离的可能
        int d1 = leftInfo.maxDistance;
        int d2 = rightInfo.maxDistance;
        int d3 = leftInfo.height + rightInfo.height + 1;
        int maxDistance = Math.max(Math.max(d1, d2), d3);
        return new Info(maxDistance, height);
    }

    public static class Info {
        int maxDistance;
        int height;
        public Info(int maxDistance, int height) {
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
}
